"""
11月14日达观数据现场面试算法题
"""

def yh_digui(n):
    """第1题，返回第n行杨辉三角的列表，递归解法"""

    # NOTE: 递归解法时间复杂度O(n^2)
    if n == 1:
        return [1, ]

    a = [1] * n
    b = yh_digui(n-1)
    for i in range(1, n-1):
        a[i] = b[i-1] + b[i]
    return a


def search_2fen(l1, k):
    """第2题，对于有序列表l1，使用二分法查找元素k的下标"""

    start = 0
    end = len(l1) - 1
    while end - start > 0:
        p = (start + end) // 2
        if l1[p] == k:
            return p
        elif l1[p] > k:
            end = p - 1
        else:
            start = p + 1

    return start


if __name__ == '__main__':
    a = yh_digui(7)
    print('-'*10 + '第1题' + '-'*10)
    print(a)

    li1 = [6, 9, 18, 33, 34, 89, 90, 93, 2000, 2001]
    k = 2000
    p = search_2fen(li1, k)
    print('-'*10 + '第2题' + '-'*10)
    print(p)
